import collections
import copy
from typing import List


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        """
        边的形式是[u, v] u<v
        如果是保持一颗树的形状的话，那么通过并查集查找会发现 所有节点的最上头的父节点都是最小的那个节点
        由此可以验证去掉一条边后还是否保持了树的形状
        """

        """
        考虑的还是不够周全 有问题
        不应该使用并查集，如果大家都是朝着父节点去的，那是可以的，但是现在是无向图
        这里的策略应该是 不断的扩展可以到达的点 直到可以到达的点的集合不变了
        """
        father = collections.defaultdict(set)
        node_num = set()
        for lID, rID in edges:
            father[lID].add(rID)
            father[rID].add(lID)
            node_num.add(lID)
            node_num.add(rID)

        node_num = len(node_num)

        print(father)

        # 不做路径优化

        def validWithoutOneEdge(edge):
            father_tmp = copy.deepcopy(father)
            lID, rID = edge
            father_tmp[lID].remove(rID)
            father_tmp[rID].remove(lID)

            def closure(nodeID):
                visited = {nodeID}
                new = {nodeID}
                while new:
                    tmp = set()
                    for nID in new:
                        for fID in father_tmp[nID]:
                            if fID not in visited:
                                tmp.add(fID)
                    visited = visited | tmp
                    new = tmp
                return visited

            for i in range(1, node_num + 1):
                i_closure = closure(i)
                print(i_closure)
                if len(i_closure) != node_num:
                    return False
            return True

        for edge in edges[::-1]:
            # print(edge)
            if validWithoutOneEdge(edge):
                return edge


edges = [[1, 3], [3, 4], [1, 5], [3, 5], [2, 3]]
edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
edges = [[1,2], [1,3], [2,3]]
print(Solution().findRedundantConnection(edges))
